package com.wang.sort;
//归并排序(递归)
public class Demo16_MergeSort {
    //递归 时间复杂度 O(logN)
    public static void mergeSort(int[] arr) {
        if(arr == null || arr.length < 2) {
            return;
        }
        process(arr, 0, arr.length - 1);

    }
    //arr[L...R]范围上变成有序
    private static void process(int[] arr, int L, int R) {
        //base case
        if(L == R) {
            return;
        }
        int mid = L + ((R - L) >> 1);
        process(arr, L, mid);
        process(arr, mid + 1, R);
        merge(arr, L, mid, R);
    }
    public static void merge(int[] arr, int L, int mid, int R) {
        int[] help = new int[R - L + 1];
        int i = 0;
        int p1 = L;
        int p2 = mid + 1;
        //循环条件 p1 p2不越界
        while (p1 <= mid && p2 <= R) {
            help[i++] = arr[p1] <= arr[p2] ? arr[p1++] : arr[p2++];
        }
        //要么p1越界，要么p2越界
        //p1未越界，把p2剩余元素放到help
        //p2未越界，把p1剩余元素放到help
        while (p1 <= mid) {
            help[i++] = arr[p2++];
        }
        while (p2 <= R) {
            help[i++] = arr[p1++];
        }
        for (int j = 0; j < help.length; j++) {
            arr[L + i] = help[i];
        }
    }
}
